package topcoder;

public class PenguinPals {

	public int findMaximumMatching(String S) {
		int n = S.length();
		int M[][] = new int[n][n];
		
		for (int i = 0; i < n; i++) 
			M[i][i] = 0;
		
		for(int j = 1; j < n; j++) {
			for(int i = j - 1; i >= 0; i--) {
				int c1 = 0;
				if (S.charAt(i) == S.charAt(j))
					c1 = M[i+1][j-1] + 1;
				int c2 = 0;
				for(int k = i; k < j; k++) 
					c2 = Math.max(c2, M[i][k] + M[k+1][j]);
				M[i][j] = Math.max(c1, c2);
			}
		}
		
		return M[0][n-1];
	}
}
